package likou;

import java.util.List;

/**
 * @author: 唐小尊
 * @email: 1171702529@qq.com
 * @cate: 2021/07/17 23:56
 */
public class _139 {
    int[] dp;

    public boolean wordBreak(String s, List<String> wordDict) {
        dp = new int[s.length()];
        return myWordBreak(s, wordDict, 0);
    }

    boolean myWordBreak(String s, List<String> wordDict, int start) {
        if (start == s.length()) {
            return true;
        }
        if (dp[start] != 0) {
            return dp[start] == 1;
        }
        for (String str : wordDict) {
            if (str.length() + start <= s.length() && s.startsWith(str, start)) {
                if (myWordBreak(s, wordDict, start + str.length())) {
                    dp[start] = 1;
                    return true;
                }
            }
        }
        dp[start] = -1;
        return false;
    }
}
